<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <title>RSA | 狼组安全团队公开知识库</title>
    <meta name="description" content="">
    <meta name="generator" content="VuePress 1.7.1">
    <link rel="icon" href="/assets/logo.svg">
    <script type="text/javascript" src="/assets/js/push.js"></script>
    <meta name="description" content="致力于打造信息安全乌托邦">
    <meta name="referrer" content="never">
    <meta name="keywords" content="知识库,公开知识库,狼组,狼组安全团队知识库,knowledge">
    <link rel="preload" href="/assets/css/0.styles.32ca519c.css" as="style"><link rel="preload" href="/assets/js/app.f7464420.js" as="script"><link rel="preload" href="/assets/js/2.26207483.js" as="script"><link rel="preload" href="/assets/js/32.7f48a571.js" as="script"><link rel="prefetch" href="/assets/js/10.55514509.js"><link rel="prefetch" href="/assets/js/11.ec576042.js"><link rel="prefetch" href="/assets/js/12.a5584a2f.js"><link rel="prefetch" href="/assets/js/13.c9f84b2e.js"><link rel="prefetch" href="/assets/js/14.d2a5440c.js"><link rel="prefetch" href="/assets/js/15.2f271296.js"><link rel="prefetch" href="/assets/js/16.0895ce42.js"><link rel="prefetch" href="/assets/js/17.627e2976.js"><link rel="prefetch" href="/assets/js/18.73745a4c.js"><link rel="prefetch" href="/assets/js/19.19350186.js"><link rel="prefetch" href="/assets/js/20.e4eac589.js"><link rel="prefetch" href="/assets/js/21.fc0657ba.js"><link rel="prefetch" href="/assets/js/22.f4a1220f.js"><link rel="prefetch" href="/assets/js/23.c8cce92d.js"><link rel="prefetch" href="/assets/js/24.46225ec2.js"><link rel="prefetch" href="/assets/js/25.9b6d75e4.js"><link rel="prefetch" href="/assets/js/26.288f535e.js"><link rel="prefetch" href="/assets/js/27.865bdc75.js"><link rel="prefetch" href="/assets/js/28.f4224fef.js"><link rel="prefetch" href="/assets/js/29.6393a40b.js"><link rel="prefetch" href="/assets/js/3.a509f503.js"><link rel="prefetch" href="/assets/js/30.d5a49f97.js"><link rel="prefetch" href="/assets/js/31.eb3647df.js"><link rel="prefetch" href="/assets/js/33.1f374ffa.js"><link rel="prefetch" href="/assets/js/34.5a911179.js"><link rel="prefetch" href="/assets/js/35.d2bcc7ef.js"><link rel="prefetch" href="/assets/js/36.42e440bd.js"><link rel="prefetch" href="/assets/js/37.dedbbdea.js"><link rel="prefetch" href="/assets/js/38.d68d1f69.js"><link rel="prefetch" href="/assets/js/39.e278f860.js"><link rel="prefetch" href="/assets/js/4.35636da8.js"><link rel="prefetch" href="/assets/js/40.97f4e937.js"><link rel="prefetch" href="/assets/js/41.38630688.js"><link rel="prefetch" href="/assets/js/42.cae56aa5.js"><link rel="prefetch" href="/assets/js/43.61a04b16.js"><link rel="prefetch" href="/assets/js/44.5c6230f2.js"><link rel="prefetch" href="/assets/js/45.0f1355ae.js"><link rel="prefetch" href="/assets/js/46.c1906649.js"><link rel="prefetch" href="/assets/js/47.7ae220ce.js"><link rel="prefetch" href="/assets/js/48.59af224e.js"><link rel="prefetch" href="/assets/js/49.6a33a171.js"><link rel="prefetch" href="/assets/js/5.08ab40ee.js"><link rel="prefetch" href="/assets/js/50.f14601d2.js"><link rel="prefetch" href="/assets/js/51.f20841fd.js"><link rel="prefetch" href="/assets/js/52.fb0a5327.js"><link rel="prefetch" href="/assets/js/53.8013048c.js"><link rel="prefetch" href="/assets/js/54.d132c2f8.js"><link rel="prefetch" href="/assets/js/55.87aa8b5d.js"><link rel="prefetch" href="/assets/js/56.161f38ad.js"><link rel="prefetch" href="/assets/js/57.bd6a2ef2.js"><link rel="prefetch" href="/assets/js/58.8a69f15a.js"><link rel="prefetch" href="/assets/js/59.93c0e2de.js"><link rel="prefetch" href="/assets/js/6.fda5ce3a.js"><link rel="prefetch" href="/assets/js/60.10091d44.js"><link rel="prefetch" href="/assets/js/61.cd1e3b10.js"><link rel="prefetch" href="/assets/js/62.9c0ad8c5.js"><link rel="prefetch" href="/assets/js/63.4a8dd9d2.js"><link rel="prefetch" href="/assets/js/64.6bf3fede.js"><link rel="prefetch" href="/assets/js/65.7a2ccc50.js"><link rel="prefetch" href="/assets/js/66.874d563b.js"><link rel="prefetch" href="/assets/js/67.bb86eab2.js"><link rel="prefetch" href="/assets/js/68.c1db2a2b.js"><link rel="prefetch" href="/assets/js/69.8141480b.js"><link rel="prefetch" href="/assets/js/7.d1fe6bef.js"><link rel="prefetch" href="/assets/js/70.9fb74c80.js"><link rel="prefetch" href="/assets/js/71.d1e4e9ab.js"><link rel="prefetch" href="/assets/js/72.e6bf83fb.js"><link rel="prefetch" href="/assets/js/73.6dd6c980.js"><link rel="prefetch" href="/assets/js/74.3612ba47.js"><link rel="prefetch" href="/assets/js/75.6e1a2434.js"><link rel="prefetch" href="/assets/js/76.5bfa4bcc.js"><link rel="prefetch" href="/assets/js/77.784df031.js"><link rel="prefetch" href="/assets/js/78.aa94a0a0.js"><link rel="prefetch" href="/assets/js/79.c4e9a4f2.js"><link rel="prefetch" href="/assets/js/8.63fd05d7.js"><link rel="prefetch" href="/assets/js/80.8d47d1f7.js"><link rel="prefetch" href="/assets/js/81.1160b022.js"><link rel="prefetch" href="/assets/js/82.7d17e5c8.js"><link rel="prefetch" href="/assets/js/83.a2ff144a.js"><link rel="prefetch" href="/assets/js/84.53d29383.js"><link rel="prefetch" href="/assets/js/9.b49161a4.js">
    <link rel="stylesheet" href="/assets/css/0.styles.32ca519c.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="ant-row"><div class="nav-button"><i aria-label="icon: bars" class="anticon anticon-bars"><svg viewBox="0 0 1024 1024" focusable="false" data-icon="bars" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M912 192H328c-4.4 0-8 3.6-8 8v56c0 4.4 3.6 8 8 8h584c4.4 0 8-3.6 8-8v-56c0-4.4-3.6-8-8-8zm0 284H328c-4.4 0-8 3.6-8 8v56c0 4.4 3.6 8 8 8h584c4.4 0 8-3.6 8-8v-56c0-4.4-3.6-8-8-8zm0 284H328c-4.4 0-8 3.6-8 8v56c0 4.4 3.6 8 8 8h584c4.4 0 8-3.6 8-8v-56c0-4.4-3.6-8-8-8zM104 228a56 56 0 1 0 112 0 56 56 0 1 0-112 0zm0 284a56 56 0 1 0 112 0 56 56 0 1 0-112 0zm0 284a56 56 0 1 0 112 0 56 56 0 1 0-112 0z"></path></svg></i> <span></span></div> <div class="ant-col ant-col-xs-24 ant-col-sm-24 ant-col-md-6 ant-col-lg-5 ant-col-xl-5 ant-col-xxl-4"><a href="/" class="router-link-active home-link"><img src="/assets/logo.svg" alt="狼组安全团队公开知识库" class="logo"> <span class="site-name">狼组安全团队公开知识库</span></a> <div class="search-box mobile-search"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div></div> <div class="ant-col ant-col-xs-0 ant-col-sm-0 ant-col-md-18 ant-col-lg-19 ant-col-xl-19 ant-col-xxl-20"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><ul role="menu" id="nav" class="ant-menu ant-menu-horizontal ant-menu-root ant-menu-light"><li role="menuitem" class="ant-menu-submenu ant-menu-submenu-horizontal ant-menu-overflowed-submenu" style="display:none;"><div aria-haspopup="true" class="ant-menu-submenu-title"><span>···</span><i class="ant-menu-submenu-arrow"></i></div></li><li role="menuitem" class="ant-menu-item"><a href="/" class="router-link-active">
          首页
        </a></li><li role="menuitem" class="ant-menu-submenu ant-menu-submenu-horizontal ant-menu-overflowed-submenu" style="display:none;"><div aria-haspopup="true" class="ant-menu-submenu-title"><span>···</span><i class="ant-menu-submenu-arrow"></i></div></li><li role="menuitem" class="ant-menu-item"><a href="/guide/">
          使用指南
        </a></li><li role="menuitem" class="ant-menu-submenu ant-menu-submenu-horizontal ant-menu-overflowed-submenu" style="display:none;"><div aria-haspopup="true" class="ant-menu-submenu-title"><span>···</span><i class="ant-menu-submenu-arrow"></i></div></li><li role="menuitem" class="ant-menu-item"><a href="/knowledge/" class="router-link-active">
          知识库
        </a></li><li role="menuitem" class="ant-menu-submenu ant-menu-submenu-horizontal ant-menu-overflowed-submenu" style="display:none;"><div aria-haspopup="true" class="ant-menu-submenu-title"><span>···</span><i class="ant-menu-submenu-arrow"></i></div></li><li role="menuitem" class="ant-menu-item"><a href="/opensource/">
          开源项目
        </a></li><li role="menuitem" class="ant-menu-submenu ant-menu-submenu-horizontal ant-menu-overflowed-submenu" style="visibility:hidden;position:absolute;"><div aria-haspopup="true" class="ant-menu-submenu-title"><span>···</span><i class="ant-menu-submenu-arrow"></i></div></li></ul> <a href="https://github.com/wgpsec" target="_blank" rel="noopener noreferrer" class="repo-link"><i aria-label="icon: github" class="anticon anticon-github"><svg viewBox="64 64 896 896" focusable="false" data-icon="github" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M511.6 76.3C264.3 76.2 64 276.4 64 523.5 64 718.9 189.3 885 363.8 946c23.5 5.9 19.9-10.8 19.9-22.2v-77.5c-135.7 15.9-141.2-73.9-150.3-88.9C215 726 171.5 718 184.5 703c30.9-15.9 62.4 4 98.9 57.9 26.4 39.1 77.9 32.5 104 26 5.7-23.5 17.9-44.5 34.7-60.8-140.6-25.2-199.2-111-199.2-213 0-49.5 16.3-95 48.3-131.7-20.4-60.5 1.9-112.3 4.9-120 58.1-5.2 118.5 41.6 123.2 45.3 33-8.9 70.7-13.6 112.9-13.6 42.4 0 80.2 4.9 113.5 13.9 11.3-8.6 67.3-48.8 121.3-43.9 2.9 7.7 24.7 58.3 5.5 118 32.4 36.8 48.9 82.7 48.9 132.3 0 102.2-59 188.1-200 212.9a127.5 127.5 0 0 1 38.1 91v112.5c.8 9 0 17.9 15 17.9 177.1-59.7 304.6-227 304.6-424.1 0-247.2-200.4-447.3-447.5-447.3z"></path></svg></i></a></nav></div></div> <!----></header> <aside class="sidebar"><div><div class="promo"><div id="promo_3"><div class="promo_title">赞助商</div> <button type="button" class="ant-btn ant-btn-primary ant-btn-background-ghost"><span>成为赞助商</span></button></div></div> <div role="separator" id="reset-margin" class="ant-divider ant-divider-horizontal ant-divider-dashed"></div></div> <ul class="sidebar-links"><li><a href="/knowledge/" aria-current="page" title="知识库广告位招租" class="sidebar-link">知识库广告位招租</a></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>CTF</span> <span class="arrow down"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/knowledge/ctf/" aria-current="page" title="分类简介" class="sidebar-link">分类简介</a></li><li><a href="/knowledge/ctf/ctf.html" title="什么是CTF？" class="sidebar-link">什么是CTF？</a></li><li><a href="/knowledge/ctf/xxe.html" title="XXE" class="sidebar-link">XXE</a></li><li><a href="/knowledge/ctf/ssrf-gopher.html" title="ssrf gopher协议" class="sidebar-link">ssrf gopher协议</a></li><li><a href="/knowledge/ctf/exec.html" title="命令执行" class="sidebar-link">命令执行</a></li><li><a href="/knowledge/ctf/PRF.html" title="伪随机数" class="sidebar-link">伪随机数</a></li><li><a href="/knowledge/ctf/php-serialize.html" title="PHP反序列化" class="sidebar-link">PHP反序列化</a></li><li><a href="/knowledge/ctf/uploadfile.html" title="文件上传" class="sidebar-link">文件上传</a></li><li><a href="/knowledge/ctf/deserialize-byte-escape.html" title="反序列化字节逃逸" class="sidebar-link">反序列化字节逃逸</a></li><li><a href="/knowledge/ctf/bypass-disable-function.html" title="bypass-disable-function" class="sidebar-link">bypass-disable-function</a></li><li><a href="/knowledge/ctf/JWT.html" title="JWT" class="sidebar-link">JWT</a></li><li><a href="/knowledge/ctf/js-prototype-chain-pollution.html" title="nodejs原型链污染" class="sidebar-link">nodejs原型链污染</a></li><li><a href="/knowledge/ctf/SSTI.html" title="SSTI" class="sidebar-link">SSTI</a></li><li><a href="/knowledge/ctf/CBC.html" title="CBC" class="sidebar-link">CBC</a></li><li><a href="/knowledge/ctf/Hash-Leng-Extension.html" title="哈希长度拓展攻击" class="sidebar-link">哈希长度拓展攻击</a></li><li><a href="/knowledge/ctf/RSA.html" aria-current="page" title="RSA" class="active sidebar-link">RSA</a></li><li><a href="/knowledge/ctf/Volatility.html" title="Volatility取证分析工具" class="sidebar-link">Volatility取证分析工具</a></li><li><a href="/knowledge/ctf/ret2text.html" title="ret2text" class="sidebar-link">ret2text</a></li><li><a href="/knowledge/ctf/ret2shellcode.html" title="ret2shellcode" class="sidebar-link">ret2shellcode</a></li><li><a href="/knowledge/ctf/ret2syscall.html" title="ret2syscall" class="sidebar-link">ret2syscall</a></li><li><a href="/knowledge/ctf/re2libc.html" title="ret2libc" class="sidebar-link">ret2libc</a></li><li><a href="/knowledge/ctf/ret2csu.html" title="ret2csu" class="sidebar-link">ret2csu</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>基础知识</span> <span class="arrow right"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>工具手册</span> <span class="arrow right"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Web安全</span> <span class="arrow right"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>攻防对抗</span> <span class="arrow right"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>代码审计</span> <span class="arrow right"><i aria-label="icon: down" class="anticon anticon-down"><svg viewBox="64 64 896 896" focusable="false" data-icon="down" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M884 256h-75c-5.1 0-9.9 2.5-12.9 6.6L512 654.2 227.9 262.6c-3-4.1-7.8-6.6-12.9-6.6h-75c-6.5 0-10.3 7.4-6.5 12.7l352.6 486.1c12.8 17.6 39 17.6 51.7 0l352.6-486.1c3.9-5.3.1-12.7-6.4-12.7z"></path></svg></i></span></p> <!----></section></li></ul></aside> <main class="page"> <div class="theme-antdocs-content content__default"><h1 id="rsa">RSA <a href="#rsa" class="header-anchor">#</a></h1> <h2 id="基本模运算及算法">基本模运算及算法 <a href="#基本模运算及算法" class="header-anchor">#</a></h2> <p>模运算是指取模运算，即求m/n的余数</p> <p>例如：</p> <p>7 mod 3 ≡ 1 -------&gt;   7 / 3 = 2 ......1</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>交换律
(a + b) mod m ≡ (b + a) mod m
(a * b) mod m ≡ (b * a) mod m
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>结合律
[(a + b) mod m + c] mod m ≡ [(a + (b + c) mod m) mod m]
[(a * b) mod m * c] mod m ≡ [(b * c) mod m * a] mod m
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>分配律
[(a + b) mod m * c] mod m ≡ [(a * c) mod m + (b * c) mod m] mod m
(a + b) mod m ≡ (a mod m + b mod m) mod m
(a - b) mod m ≡ (a mod m - b mod m) mod m
(a * b) mod m ≡ (a mod m * b mod m) mod m
a^b mod m ≡ (a mod m)^b mod m
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>模运算律
a ≡ c mod m
b ≡ d mod m

a + b ≡ (c + d) mod m
a - b ≡ (c - d) mod m
a * b ≡ (c * d) mod m
a / b ≡ (c / d) mod m
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>费马定理
如果p是素数，a为正整数且不能被p整除
a^(p-1) mod p = 1 mod p
(a^p * a^-1 * a) mod p = (1 * a) mod p 
a^p mod p = a mod p
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>欧拉定理
对于素数p
ϕ(p) = p - 1
对于素数p^t
ϕ(p^t) = p^(t) - p^(t-1)

例如：
90 = 2 * 3^2 * 5
ϕ(90) = ϕ(2) * ϕ(3^2) * ϕ(5)
	  = (2-1) * (3^2 - 3^1) * (5 - 1)
	  = 24
	  
如果 m&gt;1 a与互素
a^ϕ(m) ≡ 1 mod m

例如：
m = 11
a = 2
(2,11) = 1
ϕ(11) = 10

2^10 ≡ 1 mod 11
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>Fermat大定理
当 n &gt; 2 时
x^n + y^n = z^n(没有正整数解)
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>欧几里得算法

欧几里得算法又称为辗转相除法，是为了计算两个数的最大公约数。
定理：gcd(a,b) = gcd(b,a mod b)  (a &gt; b)

证明:
假设 a&gt;b
a = k * b + r  ------&gt; r = a - k * b  -----&gt; r = a mod b

对于充分性：
假设d 为 a,b 的一个公约数，即d = gcd(a,b)
则 a | d, b | d (a与b都能被d整除)
r = a - k * b  ----&gt; r | d 即 d = gcd(b,r)

对于必要性：
假设 d 是 gcd(b,a mod b) 的公约数  ----&gt;  b | d , r | d
因为 a = k * b + r 则 a | d  ----&gt;  d = gcd(d,b)
由上得知 gcd(a,b) 与 gcd(b,a mod b)公约数相等，所以最大公约数也相等

辗转相除到最后，gcd(x,0) = x
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><p><code>欧几里得算法c语言代码</code></p> <div class="language-c line-numbers-mode"><pre class="language-c"><code><span class="token keyword">int</span> <span class="token function">gcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
　　<span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
　　        <span class="token keyword">return</span> a<span class="token punctuation">;</span>
    <span class="token keyword">return</span>  <span class="token function">gcd</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> a <span class="token operator">%</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">gcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> r<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        r<span class="token operator">=</span>a<span class="token operator">%</span>b<span class="token punctuation">;</span><span class="token comment">//当a&lt;b时第一个循环交换他们顺序</span>
        a<span class="token operator">=</span>b<span class="token punctuation">;</span>
        b<span class="token operator">=</span>r<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>模幂运算
31^52 mod 33
ϕ(33) = ϕ(3 * 11) = ϕ(3) * ϕ(11)
	  = (3-1) * (11-1)
	  = 20
53 = 20 * 2 + 12
31^53 mod 33 = 31^12 mod 33

模平方计算
31^1 mod 33 ≡ 31
31^2 mod 33 ≡ 4
31^4 mod 33 ≡ 16
31^8 mod 33 ≡ 25

31^12 mod 33 ≡ ((31^4 * 31^8) mod 33) mod 33
			 ≡ (16 * 25) mod 33 ≡ 4
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>扩展欧几里得求逆元
若 mx ≡ 1 mod n, 则称m关于1模n的乘法逆元为x。也可表示为mx ≡ 1 (mod n)。逆元相当于数论中的倒数。

条件：
只有当gcd(m,n) = 1时,m 才有关于 模n 的逆元。

方法一:
利用费马小定理
a * a^(p-2) ≡ 1 mod p
a^(p-2)即为a关于1模p的逆元，但只能求出p为素数的情况下的乘法逆元

方法二:
采用扩展欧几里德算法来计算普遍情况下的乘法逆元
由 mx ≡ 1 mod n 
推出 
mx -kn = 1
a * x mod b = 1
ax + by = gcd(a,b) = 1 
令a=m,b=n
所求出x即为逆元
加上x = (x mod t + t) mod t 即为最小逆元

为什么可以用扩展欧几里得求得逆元？

因为ax ≡ 1 (mod p) 就是ax-yp = 1.
把y写成+的形式就是ax + py = 1，为方便理解下面我们把p写成b就是ax + by = 1。
ax = 1 - by -----&gt; ax = 1 mod b
by = 1 - ax -----&gt; by = 1 mod a
就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得定理求值
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br></div></div><p><code>欧几里得c语言代码</code></p> <div class="language-c line-numbers-mode"><pre class="language-c"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">ll <span class="token keyword">long</span> <span class="token keyword">long</span></span></span>
using namespace std<span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>p<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">exgcd</span> <span class="token punctuation">(</span>ll a<span class="token punctuation">,</span>ll b<span class="token punctuation">,</span>ll <span class="token operator">&amp;</span>x<span class="token punctuation">,</span>ll <span class="token operator">&amp;</span>y<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>b<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        x<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
        y<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> a<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">int</span> r<span class="token operator">=</span><span class="token function">exgcd</span> <span class="token punctuation">(</span>b<span class="token punctuation">,</span>a<span class="token operator">%</span>b<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> tmp<span class="token operator">=</span>x<span class="token punctuation">;</span>
    x<span class="token operator">=</span>y<span class="token punctuation">;</span>
    y<span class="token operator">=</span>tmp<span class="token operator">-</span>a<span class="token operator">/</span>b<span class="token operator">*</span>y<span class="token punctuation">;</span>
    <span class="token keyword">return</span> r<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token function">scanf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        ll x<span class="token punctuation">,</span>y<span class="token punctuation">;</span>
        <span class="token function">exgcd</span> <span class="token punctuation">(</span>i<span class="token punctuation">,</span>p<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span>
        x<span class="token operator">=</span><span class="token punctuation">(</span>x<span class="token operator">+</span>p<span class="token punctuation">)</span><span class="token operator">%</span>p<span class="token punctuation">;</span>
        <span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br></div></div><p><a href="https://blog.csdn.net/qq_41897386/article/details/82289975" target="_blank" rel="noopener noreferrer">模运算参考博客<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><a href="https://blog.csdn.net/godjing007/article/details/89608413?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-3" target="_blank" rel="noopener noreferrer">算法参考博客<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h2 id="rsa加密解密过程">RSA加密解密过程 <a href="#rsa加密解密过程" class="header-anchor">#</a></h2> <p>因为文字太过晦涩难懂，下面以图示的方法来理解RSA加密解密的过程</p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-1.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-2.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-3.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-4.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-5.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-6.png" alt=""></p> <p>以上过程中因为HACK无法得到p,q信息，也就是无法计算出d , 导致了无法解密 c 得到 m</p> <p>(n,e) 公钥</p> <p>(d,n) 私钥</p> <p>(p,q,n,e) 生成的加密必要信息</p> <p><code>必要的公式</code></p> <p>c ≡ m<sup>e</sup> mod n        -----------&gt;   (信息加密)
m ≡ c<sup>d</sup> mod n        -----------&gt;   (信息解密)
ϕ(n) = (p−1)∗(q−1)  ----------&gt;   (n的欧拉函数)
d∗e ≡ 1 mod ϕ(n)   ----------&gt;   (计算e关于ϕ(n)的逆元)</p> <h2 id="rsa攻击破解">RSA攻击破解 <a href="#rsa攻击破解" class="header-anchor">#</a></h2> <p>以下的题型全部整合在了团队的CTF平台中</p> <p><a href="https://ctf.wgpsec.org/" target="_blank" rel="noopener noreferrer">Wgpsec CTF狼组平台<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><a href="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/wgpsec-ctf/rsa/%E5%AF%86%E7%A0%81%E5%AD%A6.zip" target="_blank" rel="noopener noreferrer">例题下载<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h3 id="思路">思路 <a href="#思路" class="header-anchor">#</a></h3> <p>按照上面的流程图，可以得知，只要能知道一些关键信息就可以通过公式计算得到密文</p> <p>关于RSA需要用到的几个python模块</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>pip install gmpy2
pip install pycrypto
pip install primefac
pip install libnum
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p>分解n的网站和工具</p> <p><a href="http://factordb.com" target="_blank" rel="noopener noreferrer">分解网站<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><a href="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/yafu-1.34.zip" target="_blank" rel="noopener noreferrer">yafu下载<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>在电脑上使用python的Crypto.Uyil.number模块中的getPrime随机生成两个128bit的大素数p,q，并通过n=p*q计算n</p> <p>(isPrime是检验是否为素数)</p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-7.png" alt=""></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>p= 225417198511295800501004338813439346647
q= 235176424117170170684511636759421466507
n= 53012810680396841592836580182308344585066030484946806258181093403160673252029
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p>假设我们没有得到p,q，拿着得到的n去yafu或者网站分解</p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-8.png" alt=""></p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-9.png" alt=""></p> <p>得到了p，q的值，这样就很轻松的能得到密文了</p> <h2 id="直接模数分解n">直接模数分解N <a href="#直接模数分解n" class="header-anchor">#</a></h2> <p>例子题目</p> <p>有手就行-2💁‍♀️</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>c = 34533624647193630459864898193867716746457242698156942414136896826169638045191
n = 38915622445322594788113853812230848083133274092845339659216148461050062802771
e = 65537
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p>我们在这可以得到c,n,e的信息</p> <p>可以发现n的值并不是很大，我们使用yafu分解n值</p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/buuctf/crypto/rsa/rsa-10.png" alt=""></p> <p>得到了q,p的值为</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>q = 210984885740565358250291732634631217851
p = 184447441856923584506972548629664462921
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>在通过RSA的解密算式解密就行了</p> <p>我们只用通过p,q，求出ϕ(n)</p> <p>通过ϕ(n)得到私钥d,解密一下就是m的内容了</p> <div class="language-python line-numbers-mode"><pre class="language-python"><code><span class="token keyword">from</span> Crypto<span class="token punctuation">.</span>Util<span class="token punctuation">.</span>number <span class="token keyword">import</span> getPrime<span class="token punctuation">,</span>bytes_to_long<span class="token punctuation">,</span>long_to_bytes
<span class="token keyword">import</span> gmpy2
<span class="token keyword">import</span> libnum
<span class="token keyword">import</span> hashlib

q <span class="token operator">=</span> <span class="token number">210984885740565358250291732634631217851</span>
p <span class="token operator">=</span> <span class="token number">184447441856923584506972548629664462921</span>
c <span class="token operator">=</span> <span class="token number">34533624647193630459864898193867716746457242698156942414136896826169638045191</span>
n <span class="token operator">=</span> <span class="token number">38915622445322594788113853812230848083133274092845339659216148461050062802771</span>
e <span class="token operator">=</span> <span class="token number">65537</span>

n_ol <span class="token operator">=</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>q<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
d <span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>invert<span class="token punctuation">(</span>e<span class="token punctuation">,</span>n_ol<span class="token punctuation">)</span>
m <span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c<span class="token punctuation">,</span>d<span class="token punctuation">,</span>n<span class="token punctuation">)</span>

<span class="token keyword">print</span><span class="token punctuation">(</span>libnum<span class="token punctuation">.</span>n2s<span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">)</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><h2 id="费马分解和pollard-rho分解">费马分解和Pollard_rho分解 <a href="#费马分解和pollard-rho分解" class="header-anchor">#</a></h2> <p>因为p,q的位数太小了，导致了yafu很容易的分解出了p,q</p> <p>但是即便p,q的计算结果n非常的大，如果生成的p,q的差值过小也会导致被爆破</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>费马分解原理
n = p * q ---&gt; p,q都是大素数,奇数
所以存在 a,b 有这样的关系
a = (p + q)/2
b = (p - q)/2
n = a^2 - b^2
所以只需要枚举大于n的完全平方数，即可成功分解n
当然这里出现的原因是因为p,q之间的差值过小
导致b = (p - q)/2值较小，就可以快速分解n
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>Pollard_rho分解原理
通过某种方法获得a,b
计算 p = gcd(a-b,n)
直到p不为1，或者a,b出现循环为止，然后再判断p是否为n
如果 p = n,那么返回的n是一个质数，否则返回的p是n的一个因子
紧接着递归计算 Pollard(p) 和 Pollard(n/p)，这样就可以计算n的所有质因子
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p>这里我们只需要了解到分解n的原理和条件就行了</p> <p>这几种方法在yafu中已经可以轻松实现</p> <h2 id="公约数模数分解">公约数模数分解 <a href="#公约数模数分解" class="header-anchor">#</a></h2> <p>例子题目</p> <p>不上网的好兄弟🥦</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>e1=65537
n1=824309976713255040678774414315188911324305343946939068909416612709427405647590959202342069019687909827092434444738101792679253192217384554228922429405912765227299967576480004693502002706412618405848902047952249003683180646566555226980812871255985212785459728851482116385274886923030294336883118688943249637504111890941209117072125746914179382718841738938542647288128064878216596964710061943380933923317756767868900496106852496453030519617669299982705549374229502330525781052290174942572613344201021252879326095620935532484506572612967292839330025773029359908312962614731172968139177410904955609738349904997096375511564814382685053981249781750176436863678070180664579983017200009530939815220400486376740060465859081480696946249903279025539697834581358967123153969680757041410395146786259547823312557522601991424424780515118072828799902432329203842554206968777062590538956711084620951141331083100850610394090226480405466880324484810299761769275660553824905489329036439444269606193857756472844072315538452095272865161396795572965527449721108417342506231371917632592432396627440113643668181341007626924926752996257541349928107829776244387124514376067059436403317102173969866403920047378658985491771106094848218483420872665866345564496827
c1=619914776107204299421445515173752551578219512744832453386701408956131174382320293166571812398142061624071844793902243230988065164689738932213640598607827763120716664826659348935506492768840667618225389848502303543184323923750014314468273838436900100602616360301578680417070089037669208417514209496064782776638328659280595442584379339709690595064375146973041893766612952550104106304945793198707913036776562970941681277387345166363055403617979919206215550071922838408131362316374998986152131970583571257394242002989402779457115646413931644663555330819307049576617764087014494844129906098270686406058331758868723651041516567453323769768954687687202307774567305854473941230877789037414544400622116272774149579612412707977679341464711326395329328746997671371678549747416132575437991623923520089934467780767741968218870533906551561755021778559582638320070802534402702441689980582215813996309661425381981953031455267480573603282477682645039060338023983236132572154559608798674661049316746566458858853902292172161686826090441354261889811244610252422433735484707855667726547016802906293840413275921015090833094030889513775808522094907659133321728552859456301911921882441570565302485792013026978232768832198065043569203133298692101550276793242


e2=65537
n2=905589252405843373769915380293297111534760160714737080968066656272265067237261488456971858456917989327188732044692331992189086519820435633306176464411261896021205034205490970644012401822191880790030875680376477319350989208508591406379353590606990790187262655027873609762696926884097121412806124968361945732028625146592611563133972373222186510357547047870461524686536342088980414561620202107652793943447542030500100100438546978201140485266000991269033918263304132180594282910120350517431177243383393951480422824952551390879069092986257009179295057946730605973160346524195449500021703749379427308594689270698548425547616170119689641602115020951172647164330653185839148908281150010508830578946902028400175833666756810132914706574636302946981088249485384995123961868977200184192366871488238130493276320548228987765469367680884015794318055385681062658024380060853629777987397931994453740025625110420802340709951010187420093537470088728911794883713099533087772597248823814645583216509715894593709142551596518622892980794670674353243620390795154580419812174256794942916769770550059026084217681241980763703393095418708693297369255695621169620925250022220663830988716484961599451891633153226183322921970730586750473413763286928431026521685503
c2=673931551637686573733931629946259955273050809105413358970865200931337620800601472110603043036230330369308198862836020608370123474012622263062171294537227742055596124838615523641277612651513376399422388728998723881390750022802888924469874997383403315092150360404739350111053494140814081500234944823944838342851486117828948012785473829786919168505899092926364319233270563625167199627187969831097779544020398227294075980803974781408640110508283074795045029934267450514279868306481527002838558049458432355280575187364797865249444744186956192622171429969229590383633312442290257337521345975778920638983724068169611670153900548976779043697802190755538297452687741381067668713313038012240461367852752324450730890453516495687244181415711446356025503068925532832441729497205951722171806849453544384230181139694995076734472488950052672657187723121538897634719634849656096065795251013915979636071103988880297602168171474689743253367371894201376237227289251967333720190335216940010089300129979229084907563995802063939925492798235466279747474279314734378363118765257958698347531646918232605837643662036855703017542230709453864001404693532353827244434156882808171822447915265832615174700571049925710515965628161428609658333071907595502748554057056
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><p>如果在信息传递的过程中，不小心在两次通信中生成的大素数有一个是相同的，那么就可以通过计算n的公约数来求密文</p> <p>举一个小例子</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>n1 = 21          n2 = 27

p1 = 3			 p2 = 3

q1 = 7			 q2 = 9
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>通过 gcd(n1,n2) 求 n1,n2的公约数为 3</p> <p>再使用公式</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>q1 = n1/p1

q2 = n2/p2
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p>就可以得到p,q的值了</p> <p>接下在就行简单的解密过程了</p> <div class="language-python line-numbers-mode"><pre class="language-python"><code><span class="token keyword">from</span> Crypto<span class="token punctuation">.</span>Util<span class="token punctuation">.</span>number <span class="token keyword">import</span> getPrime
<span class="token keyword">import</span> gmpy2
<span class="token keyword">import</span> libnum

e1<span class="token operator">=</span><span class="token number">65537</span>
p1<span class="token operator">=</span><span class="token number">29008261717768474732906182649544179950245731333856747822738033258581069736557764859442064091137212340680268427765919841814967050794545225995389669474019775859945436546756236044499372530353003845881686675641839555639930200984860821453188112209554136400254884598545226639935680295845162244784506051553763186071719627985082234455247206581278772200229668817768329850670949599442836344094584680854657993521481101663964847428180681244543566290820854582896400157941001341667919766167231693578862015420077985863396707106766463482770702693985545871194934489250728689808073962247463444300011793100734752341705797978671216386783</span>
q1<span class="token operator">=</span><span class="token number">28416386501654430231634023011382380906765239866990399332431436340108491064711397713237567536296763666523646628356952301922895839797701232191691037574805309021987595282658712896258188715354825289682378642085500458887832617987265563703665762071475093524818948426458703480477759743929208116927981543222603237052735985771173613152943586906535242363863845503107606569979697961597315510194369897277252404678573252886606721258047776336698313722607174171682001084242086119017366968245890650225737466861293317900336322062217879889573106431966815073236137390496996913378630736551144302472127942702441992143356658213344341333669</span>
n1<span class="token operator">=</span><span class="token number">824309976713255040678774414315188911324305343946939068909416612709427405647590959202342069019687909827092434444738101792679253192217384554228922429405912765227299967576480004693502002706412618405848902047952249003683180646566555226980812871255985212785459728851482116385274886923030294336883118688943249637504111890941209117072125746914179382718841738938542647288128064878216596964710061943380933923317756767868900496106852496453030519617669299982705549374229502330525781052290174942572613344201021252879326095620935532484506572612967292839330025773029359908312962614731172968139177410904955609738349904997096375511564814382685053981249781750176436863678070180664579983017200009530939815220400486376740060465859081480696946249903279025539697834581358967123153969680757041410395146786259547823312557522601991424424780515118072828799902432329203842554206968777062590538956711084620951141331083100850610394090226480405466880324484810299761769275660553824905489329036439444269606193857756472844072315538452095272865161396795572965527449721108417342506231371917632592432396627440113643668181341007626924926752996257541349928107829776244387124514376067059436403317102173969866403920047378658985491771106094848218483420872665866345564496827</span>
c1<span class="token operator">=</span><span class="token number">619914776107204299421445515173752551578219512744832453386701408956131174382320293166571812398142061624071844793902243230988065164689738932213640598607827763120716664826659348935506492768840667618225389848502303543184323923750014314468273838436900100602616360301578680417070089037669208417514209496064782776638328659280595442584379339709690595064375146973041893766612952550104106304945793198707913036776562970941681277387345166363055403617979919206215550071922838408131362316374998986152131970583571257394242002989402779457115646413931644663555330819307049576617764087014494844129906098270686406058331758868723651041516567453323769768954687687202307774567305854473941230877789037414544400622116272774149579612412707977679341464711326395329328746997671371678549747416132575437991623923520089934467780767741968218870533906551561755021778559582638320070802534402702441689980582215813996309661425381981953031455267480573603282477682645039060338023983236132572154559608798674661049316746566458858853902292172161686826090441354261889811244610252422433735484707855667726547016802906293840413275921015090833094030889513775808522094907659133321728552859456301911921882441570565302485792013026978232768832198065043569203133298692101550276793242</span>
n1_ol <span class="token operator">=</span> <span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>q1<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>

e2<span class="token operator">=</span><span class="token number">65537</span>
p2<span class="token operator">=</span><span class="token number">29008261717768474732906182649544179950245731333856747822738033258581069736557764859442064091137212340680268427765919841814967050794545225995389669474019775859945436546756236044499372530353003845881686675641839555639930200984860821453188112209554136400254884598545226639935680295845162244784506051553763186071719627985082234455247206581278772200229668817768329850670949599442836344094584680854657993521481101663964847428180681244543566290820854582896400157941001341667919766167231693578862015420077985863396707106766463482770702693985545871194934489250728689808073962247463444300011793100734752341705797978671216386783</span>
q2<span class="token operator">=</span><span class="token number">31218321911758725262641264544273091969770000437195927621519348591685216690780159665370877797464593736322288823785921736299427583454269605453118914226531481670284475482887737160806536427086015247827565796216950059300727219056968512803067543969349155153638356001143776681725489817215982706453000587716366746160967415719391048527241185436934510948174134730584016161325490774552017155380553761311411397494107112131019774029088071262648041691040688770482053759445029125769594519046113288284952212077358169934371248462111374958967016120834878915693825454218907233538659018692509582497575166536325369627476902046824235247841</span>
n2<span class="token operator">=</span><span class="token number">905589252405843373769915380293297111534760160714737080968066656272265067237261488456971858456917989327188732044692331992189086519820435633306176464411261896021205034205490970644012401822191880790030875680376477319350989208508591406379353590606990790187262655027873609762696926884097121412806124968361945732028625146592611563133972373222186510357547047870461524686536342088980414561620202107652793943447542030500100100438546978201140485266000991269033918263304132180594282910120350517431177243383393951480422824952551390879069092986257009179295057946730605973160346524195449500021703749379427308594689270698548425547616170119689641602115020951172647164330653185839148908281150010508830578946902028400175833666756810132914706574636302946981088249485384995123961868977200184192366871488238130493276320548228987765469367680884015794318055385681062658024380060853629777987397931994453740025625110420802340709951010187420093537470088728911794883713099533087772597248823814645583216509715894593709142551596518622892980794670674353243620390795154580419812174256794942916769770550059026084217681241980763703393095418708693297369255695621169620925250022220663830988716484961599451891633153226183322921970730586750473413763286928431026521685503</span>
c2<span class="token operator">=</span><span class="token number">673931551637686573733931629946259955273050809105413358970865200931337620800601472110603043036230330369308198862836020608370123474012622263062171294537227742055596124838615523641277612651513376399422388728998723881390750022802888924469874997383403315092150360404739350111053494140814081500234944823944838342851486117828948012785473829786919168505899092926364319233270563625167199627187969831097779544020398227294075980803974781408640110508283074795045029934267450514279868306481527002838558049458432355280575187364797865249444744186956192622171429969229590383633312442290257337521345975778920638983724068169611670153900548976779043697802190755538297452687741381067668713313038012240461367852752324450730890453516495687244181415711446356025503068925532832441729497205951722171806849453544384230181139694995076734472488950052672657187723121538897634719634849656096065795251013915979636071103988880297602168171474689743253367371894201376237227289251967333720190335216940010089300129979229084907563995802063939925492798235466279747474279314734378363118765257958698347531646918232605837643662036855703017542230709453864001404693532353827244434156882808171822447915265832615174700571049925710515965628161428609658333071907595502748554057056</span>
n2_ol <span class="token operator">=</span> <span class="token punctuation">(</span>p2<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>q2<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>

d1 <span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>invert<span class="token punctuation">(</span>e1<span class="token punctuation">,</span>n1_ol<span class="token punctuation">)</span>
m1<span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c1<span class="token punctuation">,</span>d1<span class="token punctuation">,</span>n1<span class="token punctuation">)</span>
flag_1 <span class="token operator">=</span> libnum<span class="token punctuation">.</span>n2s<span class="token punctuation">(</span>m1<span class="token punctuation">)</span>

d2 <span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>invert<span class="token punctuation">(</span>e2<span class="token punctuation">,</span>n2_ol<span class="token punctuation">)</span>
m2<span class="token operator">=</span> gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c2<span class="token punctuation">,</span>d2<span class="token punctuation">,</span>n2<span class="token punctuation">)</span>
flag_2 <span class="token operator">=</span> libnum<span class="token punctuation">.</span>n2s<span class="token punctuation">(</span>m2<span class="token punctuation">)</span>

<span class="token keyword">print</span><span class="token punctuation">(</span><span class="token builtin">str</span><span class="token punctuation">(</span>flag_1<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token builtin">str</span><span class="token punctuation">(</span>flag_2<span class="token punctuation">)</span><span class="token punctuation">)</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br></div></div><h2 id="一个分解的例子">一个分解的例子 <a href="#一个分解的例子" class="header-anchor">#</a></h2> <p>另一种题型，给你有关n的其他有关算式</p> <p>例子：</p> <p>女朋友的聊天记录🥦</p> <p><img src="http://peiqi-boke.oss-cn-zhangjiakou.aliyuncs.com/wgpsec-ctf/peiqi-RSA-6-1.jpg" alt=""></p> <p>题目提示：peiqi=(p+520)*(q+520)</p> <p>根据给的提示分析加密过程</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>1,生成m的1~30的随机数次方 ---&gt;c1
2,用公钥(n,e)加密c1      ---&gt;c2
3,用公钥(peiqi,e)加密c2  ---&gt;c3  
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language- line-numbers-mode"><pre class="language-text"><code>n=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731402197392186162426572460924170144815459280292038798573517240473723212917475994555278140089160884080770934882248855992019482512867322735936930918031567624003424284507526700957286437082738893899468444943650565398213516262653534101927337725614414267105976588592783298584640344155571836662897588729868409203459117059
e=65537
peiqi=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731572253846238252647161985685432295738082766877396752019943012580636589164644125010073946413108951305564059881537794476457602047138719485228161010739405064157783241778448944470473298163156034126054406807297456937129548816176179704045207131224909988357244665869859061263890702529905040557579134990132844969289396259
c=5482202777490716534742001860730733245703162680164829063899425154796149111749426755752696933474476315957195654145886661833161128752650489114348801850277281013599078248459234726247608999052658393093261773012085995729908722425867518715231403283837324730986276769991562455242112930535955638946020374499583285967368081356098316200877276281391326176072541717343183325729633161998105304336388217903809696260815719456619790067591554832909766088841683629739632809828420661566086443444796658031348007908713779060772794447103923388464348339614504047304444504066194611260026519898801631578959669217929301004775518173581480779628

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>构建方程</p> <p>x^2-(p+q)x+p*q=0</p> <p>即(x-p)*(x-q)=0   -----&gt;  方程两个根即为p,q的值</p> <p>密钥peiqi可以分解为</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>peiqi = p*q + 520p + 520q + 520*520
	  = n + 520(p+q) + 520*520

(p+q) = (peiqi - n - 520*520)//520
(p*q) = n 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>有了这些再根据求根公式计算x1,x2即为p1,q1的值</p> <p>再使用 RSA 解密 2次后，爆破平方数就ok了</p> <div class="language-python line-numbers-mode"><pre class="language-python"><code><span class="token keyword">from</span> Crypto<span class="token punctuation">.</span>Util<span class="token punctuation">.</span>number <span class="token keyword">import</span> getPrime<span class="token punctuation">,</span>long_to_bytes<span class="token punctuation">,</span>bytes_to_long<span class="token punctuation">,</span>isPrime
<span class="token keyword">import</span> gmpy2
<span class="token keyword">import</span> libnum

n<span class="token operator">=</span><span class="token number">26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731402197392186162426572460924170144815459280292038798573517240473723212917475994555278140089160884080770934882248855992019482512867322735936930918031567624003424284507526700957286437082738893899468444943650565398213516262653534101927337725614414267105976588592783298584640344155571836662897588729868409203459117059</span>
e<span class="token operator">=</span><span class="token number">65537</span>
peiqi<span class="token operator">=</span><span class="token number">26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731572253846238252647161985685432295738082766877396752019943012580636589164644125010073946413108951305564059881537794476457602047138719485228161010739405064157783241778448944470473298163156034126054406807297456937129548816176179704045207131224909988357244665869859061263890702529905040557579134990132844969289396259</span>
c3<span class="token operator">=</span><span class="token number">5482202777490716534742001860730733245703162680164829063899425154796149111749426755752696933474476315957195654145886661833161128752650489114348801850277281013599078248459234726247608999052658393093261773012085995729908722425867518715231403283837324730986276769991562455242112930535955638946020374499583285967368081356098316200877276281391326176072541717343183325729633161998105304336388217903809696260815719456619790067591554832909766088841683629739632809828420661566086443444796658031348007908713779060772794447103923388464348339614504047304444504066194611260026519898801631578959669217929301004775518173581480779628</span>

pq <span class="token operator">=</span> n
paq <span class="token operator">=</span> <span class="token punctuation">(</span>peiqi<span class="token operator">-</span>n<span class="token operator">-</span><span class="token number">520</span><span class="token operator">*</span><span class="token number">520</span><span class="token punctuation">)</span><span class="token operator">//</span><span class="token number">520</span>

a<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>mpz<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>
b<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>mpz<span class="token punctuation">(</span><span class="token operator">-</span>paq<span class="token punctuation">)</span>
c<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>mpz<span class="token punctuation">(</span>n<span class="token punctuation">)</span>
i<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>mpz<span class="token punctuation">(</span>gmpy2<span class="token punctuation">.</span>iroot<span class="token punctuation">(</span>b<span class="token operator">*</span>b<span class="token operator">-</span><span class="token number">4</span><span class="token operator">*</span>a<span class="token operator">*</span>c<span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>

x1<span class="token operator">=</span><span class="token punctuation">(</span><span class="token operator">-</span>b<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token operator">//</span><span class="token number">2</span>
x2<span class="token operator">=</span><span class="token punctuation">(</span><span class="token operator">-</span>b<span class="token operator">+</span>i<span class="token punctuation">)</span><span class="token operator">//</span><span class="token number">2</span>

p1<span class="token operator">=</span>x2
q1<span class="token operator">=</span>x1
p2<span class="token operator">=</span>x2<span class="token operator">+</span><span class="token number">2</span>
q2<span class="token operator">=</span>x1<span class="token operator">+</span><span class="token number">2</span>

n1_ol<span class="token operator">=</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>q1<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
n2_ol<span class="token operator">=</span><span class="token punctuation">(</span>p1<span class="token operator">+</span><span class="token number">520</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>q1<span class="token operator">+</span><span class="token number">520</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>

d3<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>invert<span class="token punctuation">(</span>e<span class="token punctuation">,</span>n2_ol<span class="token punctuation">)</span>
m3<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c3<span class="token punctuation">,</span>d3<span class="token punctuation">,</span>peiqi<span class="token punctuation">)</span>
d2<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>invert<span class="token punctuation">(</span>e<span class="token punctuation">,</span>n1_ol<span class="token punctuation">)</span>
m2<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>m3<span class="token punctuation">,</span>d2<span class="token punctuation">,</span>n<span class="token punctuation">)</span>

<span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">30</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
	<span class="token keyword">try</span><span class="token punctuation">:</span>
		<span class="token keyword">print</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
		m1<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>iroot<span class="token punctuation">(</span>m2<span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
		<span class="token keyword">print</span><span class="token punctuation">(</span>libnum<span class="token punctuation">.</span>n2s<span class="token punctuation">(</span>m1<span class="token punctuation">)</span><span class="token punctuation">)</span>	
	<span class="token keyword">except</span><span class="token punctuation">:</span>
		<span class="token keyword">continue</span>	
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br></div></div><div class="language-python line-numbers-mode"><pre class="language-python"><code><span class="token comment">#加密方式</span>
<span class="token keyword">import</span> random
<span class="token keyword">import</span> libnum

rand <span class="token operator">=</span> random<span class="token punctuation">.</span>randint<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">30</span><span class="token punctuation">)</span>
m<span class="token operator">=</span><span class="token string">'peiqi'</span>
m<span class="token operator">=</span>libnum<span class="token punctuation">.</span>s2n<span class="token punctuation">(</span>m<span class="token punctuation">)</span>
c1<span class="token operator">=</span>m<span class="token operator">**</span>rand
c2<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c1<span class="token punctuation">,</span>e<span class="token punctuation">,</span>n<span class="token punctuation">)</span>
c3<span class="token operator">=</span>gmpy2<span class="token punctuation">.</span>powmod<span class="token punctuation">(</span>c2<span class="token punctuation">,</span>e<span class="token punctuation">,</span>peiqi<span class="token punctuation">)</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br></div></div><h2 id="小指数明文爆破">小指数明文爆破 <a href="#小指数明文爆破" class="header-anchor">#</a></h2> <p>在一般的信息传递过程中e取值为65537，又时如果e的值过小</p> <p>且满足<code>m很小，n很大，e很小</code></p> <p>就会出现</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>m^e &lt; n 
根据 c=m^e mod n
得到 c=m^e

例如
e = 3
n = 29
m = 3
c = 3^3 mod 29 ----&gt; 3^3
也就是 c=m^3,直接开根号就会得到m
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br></div></div><p>如果m^3 &gt; n 且并没有超过 n 过多</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>存在式子
k*n &lt; m^3 &lt; (k+1)*n

例如
e = 3
n = 26
m = 3
c = 3^3 mod 26----&gt; 1

k*n + c = m^3 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br></div></div><p>这里拿平台的一道例题来理解一下</p> <p>密码学表白🙆‍♂️</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>c= 70648271870529018298808886692660001235938402498859964208263409228294415956391386882206991779337601969468744143154220156908990882519717884837945906532856617909820634715854106067161582726782479804159872876992853415864029799581913231177768699278743865744051081912845185335254212638849627195499382733556635858876295634685104897939348828134359144172975276459715762939123096110061586424369639959775521808682889540769193855829876997008128536903490299132154510356729022499408881154087899262032022855765099359626306072450220026018989683836905274747226301294492449246981491703637969852470324929139841720904168369016701475473723817222435805118280228349995037458691540317562924025604518558871782328127664484684356019553232422829444404192009366087224101978739443672545344658651273357576407371982381712751927195093709853829098510072742432249637952525032152431697014721551432098156200586978917577793422057597440719114480618877894616871959869916614058028831275788375950733806459764284840487325149337299990855084479898075589047172548147875475208055116347806096743889904780424630991082111584954172971348812743549982114088569643724870601775753587500487587232004365616342285254951215710149051425199567406281845437620161540582331552889378213717815240687946879147182009028055465175524929611814188527384223348841689860466118240991278594716972892815411269840685462905179556339480041379983668015257914037862901765474982683391249869954470639078475799966417324353131574185612380759323772536955664969364984771648781609746891888279115194051967522808187234763670188472064410745331155700030125511119592595872233060513965829818176890051306809753236542584083528178867508482630064114676825193611148863808117676651877021193525941919029447722940424850259638483259618630908803708352705413985045710677257866844109324594946057235660716032547419296152445756960506166306142244870597217375420785364387192306982268095293440397581098253894684144767233449993257607977934129268826833178031802975929524501934934571709387124594721454624740923550910142337887938218289407086085953807593009004062815408946161107775999354280866956654098094276407491110119245931585538677207353167309009711825693274002853552686144987620601712501856763042883463793285988502606582149509061672725832529050936604314856886070993609898668742138501623378819838961657769663146089896801201156992228867361774391692716488518726007591552311991840025005427255145632627726384869513359648324145841090361264259057089609185017730717955467211726509629

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>这一题里面只看到了c,并没有看到其他的线索</p> <p>看一下题目提示</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>你终于鼓起了勇气向女神表白了,但是女神的密码学tqllllllll

🤵 : aV9sb3ZlX3lvdQ==

🤹‍♂️ : 7064827187052901829880.........

🤵 : 😐

🤹‍♂️ : 等你搞清楚RSA的 c = m^e mod n 你就知道了
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><p>这里提示 c = m^e mod n</p> <p>可以猜到这题只能是刚刚讲的小指数明文爆破了</p> <p>根据 m^e &lt; n</p> <p>得到 c = m^e</p> <p>编写程序爆破e就行了</p> <div class="language-python line-numbers-mode"><pre class="language-python"><code><span class="token keyword">from</span> Crypto<span class="token punctuation">.</span>Util<span class="token punctuation">.</span>number <span class="token keyword">import</span> getPrime<span class="token punctuation">,</span>long_to_bytes<span class="token punctuation">,</span>bytes_to_long<span class="token punctuation">,</span>isPrime
<span class="token keyword">import</span> gmpy2
<span class="token keyword">import</span> libnum

c<span class="token operator">=</span><span class="token number">7003953316963512304871139095211587993231123079291276945893763719959022240323069861041889815470643001299144947906274214388649617226033483962907980966853900663707585777649029162126238584277221873896766269480082618794525046351292909945659944292239052902810926099687167064811308033422459878461718134674002794768012891191252372328863603097947733980803194086307439598740909206593761856769699411851492692178913409032787606966067770304577962207797482307447844609835379279861719221580965045441176112832476043909330229525987723381894539303624464852545509270859918281262716949347750758972067923083236412130627905223127205142891163614768682817975295680866670405407880188855880293550321473460862230334726201421803013928471811099805692874844439391901456256276080565719981113677564845163001177683109687874157233055585508685647723265350544758428813903168728441549480759211100253407150847147382204992321123361503291604382645174487172534780978245775544538142604124222495493710060567737833161772359866283722481235261956476301455855983034142876174625258145548881077378791457711002290893942609172083708624223985585277312269238430952655386545189064168555461372116400801528354776128989477399459824001155917788308808042846810679642130604601568375010115916215813791441796821302353449671679062548523950749139607284358759827951717130878998700655308049733817036632749643751688935798198565174419801968716714776979226954509048678843207860410626556815809113831844395492582651269999193028511021985235012725795056131092156086021943624679453475385808194450775990758459892919126722634096576404595530275737735351801468718889436545645773134234604771827253235835754394477464047353224103053451153593127784790714628053776006414035734003004034989658814088119155665409072397248919342545815133560011673719564110407250894232179249650236390874948360250438719165497109572081139490306201401312343273868584103057978764726955782874768654917837185121357706391927294706177352964396082214488571931801912011605313211221931849029564918957272107516639099748929805640115760421342978166507444649756183189506298417295578158674520937821373129304044849974615924293291353698024515263022400465589696649352245838506359590305510294609046869715367191484039429315726474125636140119490583036055026146203364697125987090473653107687491340392043693998450421007886343014982214578894366636829436256595539986254228541</span>

e<span class="token operator">=</span><span class="token number">1</span>

<span class="token keyword">while</span> <span class="token boolean">True</span><span class="token punctuation">:</span>
	<span class="token keyword">try</span><span class="token punctuation">:</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>gmpy2<span class="token punctuation">.</span>iroot<span class="token punctuation">(</span>c<span class="token punctuation">,</span>e<span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token boolean">True</span><span class="token punctuation">)</span><span class="token punctuation">:</span>	
			<span class="token keyword">print</span><span class="token punctuation">(</span>libnum<span class="token punctuation">.</span>n2s<span class="token punctuation">(</span>gmpy2<span class="token punctuation">.</span>iroot<span class="token punctuation">(</span>c<span class="token punctuation">,</span>e<span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
			<span class="token keyword">break</span>
		e<span class="token operator">=</span>e<span class="token operator">+</span><span class="token number">1</span>
		<span class="token keyword">print</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span>
	<span class="token keyword">except</span><span class="token punctuation">:</span>
		e<span class="token operator">=</span>e<span class="token operator">+</span><span class="token number">1</span>
		<span class="token keyword">print</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span>
		<span class="token keyword">continue</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br></div></div></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">12/18/2021, 12:46:42 PM</span></div></footer> <div class="page-nav"><p class="inner"><span class="prev"><a href="/knowledge/ctf/Hash-Leng-Extension.html" class="prev"><i aria-label="icon: left" class="anticon anticon-left"><svg viewBox="64 64 896 896" focusable="false" data-icon="left" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M724 218.3V141c0-6.7-7.7-10.4-12.9-6.3L260.3 486.8a31.86 31.86 0 0 0 0 50.3l450.8 352.1c5.3 4.1 12.9.4 12.9-6.3v-77.3c0-4.9-2.3-9.6-6.1-12.6l-360-281 360-281.1c3.8-3 6.1-7.7 6.1-12.6z"></path></svg></i>
        哈希长度拓展攻击
      </a></span> <span class="next"><a href="/knowledge/ctf/Volatility.html">
        Volatility取证分析工具
        <i aria-label="icon: right" class="anticon anticon-right"><svg viewBox="64 64 896 896" focusable="false" data-icon="right" width="1em" height="1em" fill="currentColor" aria-hidden="true"><path d="M765.7 486.8L314.9 134.7A7.97 7.97 0 0 0 302 141v77.3c0 4.9 2.3 9.6 6.1 12.6l360 281.1-360 281.1c-3.9 3-6.1 7.7-6.1 12.6V883c0 6.7 7.7 10.4 12.9 6.3l450.8-352.1a31.96 31.96 0 0 0 0-50.4z"></path></svg></i></a></span></p></div> </main> <!----></div><div class="global-ui"></div></div>
    <script src="/assets/js/app.f7464420.js" defer></script><script src="/assets/js/2.26207483.js" defer></script><script src="/assets/js/32.7f48a571.js" defer></script>
  </body>
</html>